package implementations;


public class QuickImplementation {
	

	public int[] quickSort(int[] lista, int comecoDaLista, int fimDaLista) {
		
		if (comecoDaLista >= fimDaLista) {
			return lista;}
		 
		int indiceDoPivo = partition(lista, comecoDaLista, fimDaLista);
		quickSort(lista, comecoDaLista, fimDaLista-1);
		quickSort(lista, comecoDaLista+1, fimDaLista);		
		
		return lista;
	}
	
	private int partition(int[] lista, int comecoDaLista, int fimDaLista) {
		int i = comecoDaLista + 1; // segundo elemento da lista
		int j = fimDaLista;
		int pivo = lista[comecoDaLista]; // primeiro elemento da lista
		
		while(i <= j) {   // enquanto o segundo elemento for melhor que o ultimo
			if (lista[i] <= pivo) { // compare o segundo da lista com o pivo
				i++; // pegue o proximo - incremento
			} else if (lista[j] > pivo){ // se o ultimo elemento for maior que o pivo
				j--; // pegue o anterior ao ultimo - decremente
			} else {
				lista = swap(lista, i, j);
			}
		}
		lista = swap(lista, comecoDaLista, i-1);
		return i-1;  // Q
	}
	

	private int[] swap(int[] lista, int menor, int maior) {
		int varTemp = lista[maior];
		lista[maior] = lista[menor];
		lista[menor] = varTemp;
		
		return lista;
	}
}